package io.tec.cloud.algorithm.c01_v20220601;

import java.time.LocalDateTime;
import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * 在一个有序数组中，找某个数是否存在
 */
public class BinarySearch {

    public static boolean exist(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0, R = arr.length - 1, mid;
        // 循环的条件：区间至少两个数；
        // 最后一次循环结束时，mid==L
        // 如果arr[mid] > target，继续看左边，实际上是target在数组中不存在的情况；
        // 如果arr[mid] < target，继续看右边，此时L=R，并退出循环。
        // 再判断下arr[L] == target或者arr[R] == target;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] > target) {
                R = mid - 1;
            } else if (arr[mid] < target) {
                L = mid + 1;
            }
        }
//        return arr[L] == target;
        return arr[R] == target;
    }

    public static boolean exist2(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0, R = arr.length - 1, mid;
        // 循环条件为区间至少有一个数，即L=R；
        // 退出循环前，L==Mid==R <> Target，所以退出循环后，直接返回false。
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] > target) {
                R = mid - 1;
            } else if (arr[mid] < target) {
                L = mid + 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int testTime = 500_0000;
        int maxValue = 100;
        int maxLength = 50;
        System.out.println(LocalDateTime.now());
        for (int i = 0; i < testTime; i++) {
            int[] arr = SortTestUtil.generatorRandomArray(maxValue, maxLength);
            int target = genTarget(arr);
            arr = Arrays.stream(arr).sorted().toArray();
//            SortTestUtil.p(arr);
//            System.out.println(target);
//            System.out.println();
            boolean f1 = exist(arr, target);
            boolean f2 = compareExist(arr, target);
            boolean f3 = compareExistBySet(arr, target);
            boolean f4 = exist2(arr, target);
            if (f1 != f2 || f1 != f3 || f1 != f4) {
                SortTestUtil.p(arr);
                System.out.println(target);
                System.out.println("error");
                break;
            }
        }
        System.out.println(LocalDateTime.now());
        System.out.println("finish");

    }

    private static boolean compareExist(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return true;
            }
        }
        return false;
    }

    private static boolean compareExistBySet(int[] arr, int target) {
        return IntStream.of(arr).filter(i -> i == target).findAny().isPresent();
    }

    private static int genTarget(int[] arr) {
        return Math.random() > 0.5 ? arr[(int) (Math.random() * arr.length)] : (int) (Math.random() * arr.length * arr.length);
    }
}
